{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Difference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTheDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找不同"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串 <code>s</code> 和 <code>t</code>&nbsp;，它们只包含小写字母。</p>\n",
    "\n",
    "<p>字符串 <code>t</code>&nbsp;由字符串 <code>s</code> 随机重排，然后在随机位置添加一个字母。</p>\n",
    "\n",
    "<p>请找出在 <code>t</code>&nbsp;中被添加的字母。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcd\", t = \"abcde\"\n",
    "<strong>输出：</strong>\"e\"\n",
    "<strong>解释：</strong>'e' 是那个被添加的字母。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"\", t = \"y\"\n",
    "<strong>输出：</strong>\"y\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>t.length == s.length + 1</code></li>\n",
    "\t<li><code>s</code> 和 <code>t</code> 只包含小写字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-difference](https://leetcode.cn/problems/find-the-difference/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-difference](https://leetcode.cn/problems/find-the-difference/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcd\"\\n\"abcde\"', '\"\"\\n\"y\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        char_count = {}\n",
    "        \n",
    "        for char in s:\n",
    "            if char in char_count:\n",
    "                char_count[char] += 1\n",
    "            else:\n",
    "                char_count[char] = 1\n",
    "\n",
    "        for char in t:\n",
    "            if char in char_count and char_count[char] > 0:\n",
    "                char_count[char] -= 1\n",
    "            else:\n",
    "                return char\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        t = list(t)\n",
    "        for i in s:\n",
    "            t.remove(i)\n",
    "        return t[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic = {}\n",
    "        for i in t:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        for j in s:\n",
    "            if j in dic:\n",
    "                dic[j] -= 1\n",
    "            else:\n",
    "                dic[j] = 1\n",
    "        for k,v in dic.items():\n",
    "            if v > 0:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\r\n",
    "        s_len = len(t)\r\n",
    "        ans = {}\r\n",
    "        for i in range(s_len-1):\r\n",
    "            if s[i] in ans:\r\n",
    "                ans[s[i]] += 1\r\n",
    "            else :\r\n",
    "                ans[s[i]] = 1\r\n",
    "            if t[i] in ans:\r\n",
    "                ans[t[i]] -= 1 \r\n",
    "            else :\r\n",
    "                ans[t[i]] = -1\r\n",
    "        if t[s_len-1] in ans:\r\n",
    "            ans[t[s_len-1]] -= 1\r\n",
    "        else :\r\n",
    "            ans[t[s_len-1]] = -1\r\n",
    "        for k,v in ans.items():\r\n",
    "            if v != 0:\r\n",
    "                return k\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "  def findTheDifference(self, s, t):\n",
    "      dic = {}\n",
    "      for tt in t:\n",
    "          if tt not in dic:\n",
    "              dic[tt] = 1\n",
    "          else:\n",
    "              dic[tt] += 1\n",
    "      for ss in s:\n",
    "          dic[ss] -= 1\n",
    "      for ch in dic:\n",
    "          if dic[ch] == 1:\n",
    "              return ch\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        ans = t\n",
    "        if len(s) == 0:\n",
    "            return ans\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            if s[i] in ans:\n",
    "                ans = ans.replace(s[i],'',1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        ans = 0\n",
    "        for i in (s+t):\n",
    "            ans ^= ord(i)\n",
    "        return chr(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        s_list = list(s)\n",
    "        t_list = list(t)\n",
    "        \n",
    "        for i in s_list:\n",
    "            t_list.remove(i)\n",
    "        \n",
    "        result = ''\n",
    "        for i in t_list:\n",
    "            result = result + i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        # 参考评论\n",
    "        m = s + t # 拼接\n",
    "        for i in m: # 遍历所有元素\n",
    "            # count()函数用于统计字符串或列表中某个元素出现的次数\n",
    "            if m.count(i) % 2 == 1: # 出现次数不是偶数\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic = {}\n",
    "        for tt in t:\n",
    "            if tt not in dic:\n",
    "                dic[tt] = 1\n",
    "            else:\n",
    "                dic[tt] += 1\n",
    "        for ss in s:\n",
    "            dic[ss] -= 1\n",
    "        for key in dic:\n",
    "            if dic[key] == 1:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        for ch in t:\n",
    "            if t.count(ch) > s.count(ch):\n",
    "                return ch\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        return chr(sum(map(ord,t))-sum(map(ord,s)))            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        return (Counter(t) -Counter(s)).popitem()[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        return chr(sum(map(ord, t)) - sum(map(ord, s)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        result = 0\n",
    "        for char in t:\n",
    "            result ^= ord(char)\n",
    "        for char in s:\n",
    "            result ^= ord(char)\n",
    "        return chr(result)\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        return chr(sum(map(ord, t)) - sum(map(ord, s)))\n",
    "       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "  def findTheDifference(self, s, t):\n",
    "      dic = {}\n",
    "      for tt in t:\n",
    "          if tt not in dic:\n",
    "              dic[tt] = 1\n",
    "          else:\n",
    "              dic[tt] += 1\n",
    "      for ss in s:\n",
    "          dic[ss] -= 1\n",
    "      for ch in dic:\n",
    "          if dic[ch] == 1:\n",
    "              return ch\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        result = 0\n",
    "        for char in s:\n",
    "            result ^= ord(char)\n",
    "        for char in t:\n",
    "            result ^= ord(char)\n",
    "        return chr(result)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        if len(s) == 0:\n",
    "            return t\n",
    "\n",
    "        table = [0] * 26\n",
    "        for i in range(len(t)):\n",
    "            if i < len(s):\n",
    "                table[ord(s[i])-ord('a')] -= 1\n",
    "            table[ord(t[i]) - ord('a')] += 1\n",
    "\n",
    "        for i in range(26):\n",
    "            if table[i] != 0:\n",
    "                return chr(i+97)\n",
    "\n",
    "        return 'a'\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dict = {}\n",
    "        for i in range(0,len(s)):\n",
    "            key = s[i]\n",
    "            res = \"\"\n",
    "            if key not in dict.keys():\n",
    "               dict[key] = 1\n",
    "            else:\n",
    "               dict[key] = dict[key] + 1\n",
    "\n",
    "        for i in range(0,len(t)):\n",
    "            key = t[i]\n",
    "            if key not in dict.keys():\n",
    "               res = key\n",
    "               break\n",
    "            elif dict[key] <= 0 :\n",
    "               res = key\n",
    "               break\n",
    "            else:\n",
    "               dict[key] = dict[key] - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        s, t = sorted(s) + [' '], sorted(t)\n",
    "        for c1, c2 in zip(s, t):\n",
    "            if c1 != c2: return c2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        ssum = 0\n",
    "        tsum = 0\n",
    "        for i in s:\n",
    "            ssum += ord(i)\n",
    "        for i in t:\n",
    "            tsum += ord(i)\n",
    "        diff = tsum - ssum\n",
    "        return chr(diff)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        n = ord(t[-1])\n",
    "        for i in range(len(s)):\n",
    "            n ^= ord(s[i]) ^ ord(t[i])\n",
    "        return chr(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic_s = Counter(s)\n",
    "        dic_t = Counter(t)\n",
    "        for i in dic_t :\n",
    "            if dic_s[i] != dic_t[i] or i not in dic_s:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        return chr(reduce(xor, map(ord, chain(s, t))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        s_ascii = t_ascii = 0\n",
    "        for i in range(len(s)):\n",
    "            s_ascii += ord(s[i])\n",
    "        for j in range(len(t)):\n",
    "            t_ascii += ord(t[j])\n",
    "        return chr(t_ascii-s_ascii)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # resort = out = ''\n",
    "        # ss = s\n",
    "        # for i in range(len(t)):\n",
    "        #     for j in range(len(ss)):\n",
    "        #         if t[i] == ss[j]:\n",
    "        #             resort += t[i]\n",
    "        #             ss = ss[:j] + ss[j+1:]\n",
    "        #             break\n",
    "        # if s == '':\n",
    "        #     out = t\n",
    "        # elif resort == t[:-2]:\n",
    "        #     out = t[-1]\n",
    "        # else:\n",
    "        #     for i in range(len(t)-1):\n",
    "        #         if t[i] != resort[i]:\n",
    "        #             out = t[i]\n",
    "        # return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic_s = Counter(s)\n",
    "        dic_t = Counter(t)\n",
    "        for i in dic_t :\n",
    "            if dic_s[i] != dic_t[i] or i not in dic_s:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        s = sorted(s)\n",
    "        t = sorted(t)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != t[i]:\n",
    "                return t[i]\n",
    "        else:\n",
    "            return t[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        for char in t:\n",
    "            if char not in s or s.count(char) != t.count(char):\n",
    "                return char\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dicta = {}\n",
    "        for i in t:\n",
    "            if i not in dicta:\n",
    "                dicta[i] = 1\n",
    "            else:\n",
    "                dicta[i] += 1\n",
    "        for j in s:\n",
    "            dicta[j] -= 1\n",
    "        for dicta_ in dicta:\n",
    "            if dicta[dicta_] == 1:\n",
    "                return dicta_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        \n",
    "        array_s = list(s)\n",
    "        array_t = list(t)\n",
    "        array_s.sort()\n",
    "        array_t.sort()\n",
    "        l = len(array_s)\n",
    "        \n",
    "        for i in range(l):\n",
    "            if array_s[i] != array_t[i]:\n",
    "                return array_t[i]\n",
    "\n",
    "        return array_t[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        d_s={}\n",
    "        for c in 'abcdefghijklmnopqrstuvwxyz':\n",
    "            d_s[c]=0\n",
    "        for c in s:\n",
    "            d_s[c]+=1\n",
    "        for c in t:\n",
    "            d_s[c]-=1\n",
    "            if d_s[c]<0:\n",
    "                return c\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        n=len(s)\n",
    "        if n==0:\n",
    "            return t\n",
    "        if n>=1:\n",
    "            a=sorted(s)\n",
    "            b=sorted(t)\n",
    "            if a==b[:n:]:\n",
    "                return b[n]\n",
    "            else:\n",
    "                for i in range(n):\n",
    "                    if a[i]!=b[i]:\n",
    "                        return b[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:   \n",
    "        res = 0\n",
    "        for i in s + t :\n",
    "            res ^= ord(i)  \n",
    "        return chr(res)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        ss = {}\n",
    "        for i in s:\n",
    "            if i not in ss:\n",
    "                ss[i]= 1\n",
    "            else:\n",
    "                ss[i]+=1\n",
    "        \n",
    "\n",
    "        for j in t:\n",
    "            if j not in ss:\n",
    "                return j\n",
    "            else:\n",
    "                ss[j]-=1\n",
    "                if ss[j] < 0:\n",
    "                    return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        str1=s+t\n",
    "        for i in str1:\n",
    "            if str1.count(i)%2==1:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        r = 0\n",
    "        for i in s:\n",
    "            r ^= ord(i)\n",
    "        for i in t:\n",
    "            r ^= ord(i)\n",
    "        return chr(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        i = 0\n",
    "        len_s = len(s)\n",
    "        s = sorted(s)\n",
    "        t = sorted(t)\n",
    "        while i < len_s:\n",
    "            if s[i] != t[i]:\n",
    "                return t[i]\n",
    "            i += 1\n",
    "        return t[-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "\n",
    "        seen = set(s)\n",
    "        #s = list(s)\n",
    "        #t = list(t)\n",
    "\n",
    "        for i in t:\n",
    "            if i not in seen:\n",
    "                return i\n",
    "\n",
    "        dict_s = {}\n",
    "        dict_t = {}\n",
    " \n",
    "        for i in s:\n",
    "            if i not in dict_s.keys():\n",
    "                dict_s[i] = 1\n",
    "            else:\n",
    "                dict_s[i] += 1\n",
    "        \n",
    "        for i in t:\n",
    "            if i not in dict_t.keys():\n",
    "                dict_t[i] = 1\n",
    "            else:\n",
    "                dict_t[i] += 1\n",
    "        \n",
    "        for i in dict_t.keys():\n",
    "            if dict_s[i] != dict_t[i]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        sum = 0\n",
    "        for i in s+t:\n",
    "          sum ^= ord(i) \n",
    "        return chr(sum)    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        v=0\n",
    "        for i in range(len(t)):\n",
    "            v+=ord(t[i])\n",
    "        for i in range(len(s)):\n",
    "            v-=ord(s[i])\n",
    "        return chr(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic_s = Counter(s)\n",
    "        dic_t = Counter(t)\n",
    "        for i in dic_t :\n",
    "            if dic_s[i] != dic_t[i] or i not in dic_s:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic_s = Counter(s)\n",
    "        dic_t = Counter(t)\n",
    "        for i in dic_t :\n",
    "            if dic_s[i] != dic_t[i] or i not in dic_s:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        # dic={}\n",
    "        # for i in s:\n",
    "        #     dic[i]=1 if i not in dic else dic[i]+1\n",
    "\n",
    "        # for i in t:\n",
    "        #     if i in dic:\n",
    "        #         if dic[i]==1:\n",
    "        #             del dic[i]\n",
    "        #         else:\n",
    "        #             dic[i] -= 1\n",
    "        #     else:\n",
    "        #         return i\n",
    "\n",
    "        dic={}\n",
    "        for i in t:\n",
    "            dic[i]=1 if i not in dic else dic[i]+1\n",
    "        for i in s:\n",
    "            dic[i]-=1\n",
    "        \n",
    "        for i in dic:\n",
    "            if dic[i]==1:\n",
    "                return i\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        s=list(s)\n",
    "        t=list(t)\n",
    "        s.sort()\n",
    "        t.sort()\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i]!=t[i]:\n",
    "                return t[i]\n",
    "        return t[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        data_dict = {}\n",
    "        for data in s:\n",
    "            if data_dict.get(data):\n",
    "                data_dict[data] += 1\n",
    "            else:\n",
    "                data_dict[data] = 1\n",
    "        \n",
    "        for data in t:\n",
    "            if data_dict.get(data):\n",
    "                data_dict[data] -= 1\n",
    "                if data_dict[data] < 0:\n",
    "                    return data\n",
    "            else:\n",
    "                return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        for i in t:\n",
    "            if s.count(i) != t.count(i):\n",
    "                return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        return list((collections.Counter(t)-collections.Counter(s)).keys())[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        d1 = collections.Counter(s)\n",
    "        d2 = collections.Counter(t)\n",
    "        return list((d2-d1).elements())[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        d1 = {}\n",
    "        for i in s:\n",
    "            d1[i] = d1.get(i, 0) + 1\n",
    "        for j in t:\n",
    "            if j in d1 and d1[j] > 0:\n",
    "                d1[j] -= 1\n",
    "            else:\n",
    "                return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        ans=0\n",
    "        for i in s:\n",
    "            ans^=ord(i)\n",
    "        for i in t:\n",
    "            ans^=ord(i)\n",
    "        return chr(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        sum = 0\n",
    "        for i in s+t:\n",
    "          sum ^= ord(i) #转化为整数后异或运算\n",
    "        return chr(sum)    #剩下的就是不同的字母\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        sum1=0\n",
    "        sum2=0\n",
    "        a=0\n",
    "        for i in range(len(s)):\n",
    "            sum1 += ord(s[i])\n",
    "        for j in range(len(t)):\n",
    "            sum2 += ord(t[j])\n",
    "        a=sum2 - sum1\n",
    "        return chr(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        cnt = [0] * 26\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "        for c in t:\n",
    "            cnt[ord(c) - ord('a')] -= 1\n",
    "            if cnt[ord(c) - ord('a')] == -1: return c \n",
    "        return 'a'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic = {}\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in dic:\n",
    "                dic[s[i]] = 1\n",
    "            else:\n",
    "                dic[s[i]] += 1\n",
    "        for i in range(len(t)):\n",
    "            if t[i] not in dic:\n",
    "                return t[i]\n",
    "            else:\n",
    "                dic[t[i]] -= 1\n",
    "        \n",
    "        for key,value in dic.items():\n",
    "            if value==-1:\n",
    "                return key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        added_char = 0\n",
    "\n",
    "        for char in s + t:\n",
    "            added_char ^= ord(char)\n",
    "\n",
    "        return chr(added_char)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        ans = 0\n",
    "        lst = [ord(_) for _ in s+t]\n",
    "        for i in lst:\n",
    "            ans ^= i\n",
    "        return chr(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        for char in t:\n",
    "            if char not in s or s.count(char) < t.count(char):\n",
    "                return char\n",
    "\n",
    "\n",
    "# 两种情况：加了一个新字母 or 价格一个重复的字母\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        count = collections.Counter(s)  \n",
    "        for c in t:\n",
    "            if count[c] == 0:\n",
    "                return c  \n",
    "            count[c] -= 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        ans=0\n",
    "        for i in range(len(t)):\n",
    "            ans^=ord(t[i])\n",
    "        for j in range(len(s)):\n",
    "            ans^=ord(s[j])\n",
    "        return chr(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        sum_s = sum_t = 0\n",
    "        for str_s in s:\n",
    "            sum_s += ord(str_s)\n",
    "        for str_t in t:\n",
    "            sum_t += ord(str_t)\n",
    "        \n",
    "        return chr(sum_t - sum_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic={}\n",
    "        for i in s:\n",
    "            dic[i]=1 if i not in dic else dic[i]+1\n",
    "\n",
    "        for i in t:\n",
    "            if i in dic:\n",
    "                if dic[i]==1:\n",
    "                    del dic[i]\n",
    "                else:\n",
    "                    dic[i] -= 1\n",
    "            else:\n",
    "                return i\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        count = [0 for i in range(26)]\n",
    "        for i in range(len(s)):\n",
    "            count[ord(s[i]) - ord('a')] += 1\n",
    "            count[ord(t[i]) - ord('a')] -= 1\n",
    "        count[ord(t[-1]) - ord('a')] -= 1\n",
    "        for i in range(26):\n",
    "            if count[i] == -1:\n",
    "                return chr(i + ord('a'))\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        nt=len(t);ns=[]\n",
    "        for i in range(nt-1):\n",
    "            ns.append(s[i])\n",
    "        for i in range(nt):\n",
    "            if t[i] in ns:\n",
    "                ns.remove(t[i])\n",
    "                continue\n",
    "            else:\n",
    "                return t[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic = {}\n",
    "        list = []\n",
    "        for i in t:\n",
    "            if i not in dic:\n",
    "                dic[i] = 1\n",
    "            else:\n",
    "                dic[i] +=1\n",
    "        for j in s:\n",
    "            dic[j] -= 1\n",
    "        for ch in dic:\n",
    "            if dic[ch] == 1:\n",
    "                list.append(ch)\n",
    "        return ''.join(list)\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic = {}\n",
    "        for str_s in s:\n",
    "            if str_s not in dic:\n",
    "                dic[str_s] = 1\n",
    "            else:\n",
    "                dic[str_s] += 1\n",
    "        \n",
    "        for str_t in t:\n",
    "            if str_t not in dic:\n",
    "                return str_t\n",
    "            else:\n",
    "                dic[str_t] -= 1\n",
    "                if dic[str_t] < 0:\n",
    "                    return str_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        # 可用Counter函数直接+-&|运算，再element返回迭代器再list处理\n",
    "        # return list((collections.Counter(t) - collections.Counter(s)).elements())[0]\n",
    "\n",
    "        # 可异或运算，要转ASCLL码\n",
    "        n = 0\n",
    "        for i in s:\n",
    "            n ^= ord(i)\n",
    "        for j in t:\n",
    "            n ^= ord(j)\n",
    "        return chr(n)\n",
    "\n",
    "        # 用Counter的类似字典的方法，如.values(),.items()\n",
    "        c_s = Counter(s)\n",
    "        c_t = Counter(t)\n",
    "        for i, x in c_t.items():\n",
    "            if i not in c_s or c_s[i] < x:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        ans=0\n",
    "        for i in range(len(t)):\n",
    "            ans^=ord(t[i])\n",
    "        for j in range(len(s)):\n",
    "            ans^=ord(s[j])\n",
    "        return chr(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        return list(Counter(t) - Counter(s))[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        ans=0\n",
    "        for i in range(len(t)):\n",
    "            ans^=ord(t[i])\n",
    "        for j in range(len(s)):\n",
    "            ans^=ord(s[j])\n",
    "        return chr(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        sum = 0\n",
    "        for i in t:\n",
    "          sum+=ord(i)\n",
    "        for j in s:\n",
    "          sum-=ord(j)\n",
    "        return chr(sum)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        s, t = sorted(s) + [' '], sorted(t)\n",
    "        for c1, c2 in zip(s, t):\n",
    "            if c1 != c2: return c2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        s_arr = list(s)\n",
    "        t_arr = list(t)\n",
    "        s_arr.sort()\n",
    "        t_arr.sort()\n",
    "        n = len(s_arr)\n",
    "        for i in range(n):\n",
    "            if s_arr[i] != t_arr[i]:\n",
    "                return t_arr[i]\n",
    "\n",
    "        return t_arr[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        s1=set(t)\n",
    "        for i in s1:\n",
    "            if t.count(i)>s.count(i):\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        dic = {}\n",
    "        for str_s in s:\n",
    "            if str_s not in dic:\n",
    "                dic[str_s] = 1\n",
    "            else:\n",
    "                dic[str_s] += 1\n",
    "        \n",
    "        for str_t in t:\n",
    "            if str_t not in dic:\n",
    "                return str_t\n",
    "            else:\n",
    "                dic[str_t] -= 1\n",
    "                if dic[str_t] < 0:\n",
    "                    return str_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        s, t = sorted(s)+[' '], sorted(t)\n",
    "        for i, j in zip(s, t):\n",
    "            if i != j:\n",
    "                return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s: str, t: str) -> str:\n",
    "        if len(t) == 1 or len(s) == 0:\n",
    "            return t\n",
    "        s = list(s)\n",
    "        t = list(t)\n",
    "        # i = 0\n",
    "        # while i < len(s):\n",
    "        #     j = 0\n",
    "        #     while j < len(t):\n",
    "        #         if s[i] == t[j]:\n",
    "        #             del t[j]\n",
    "        #         else:\n",
    "        #             j += 1\n",
    "        #     i += 1\n",
    "        # m = \"\".join(t)            \n",
    "        # return m\n",
    "        for char in s:\n",
    "            if char in t:\n",
    "                t.remove(char)\n",
    "        m = \"\".join(t)\n",
    "        return m"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
